package com.csdemos.algs.sets;

import java.util.HashMap;

public class DisjointSet {
	
	private HashMap<Integer, Integer> p;
	private HashMap<Integer, Integer> rank;
	
	public DisjointSet() {
		p = new HashMap<Integer, Integer>();
		rank = new HashMap<Integer, Integer>();
	}
	
	public void makeSet(int x) {
		p.put(x, x);
		rank.put(x, 0);
		
	}
	
	public void union(int x, int y) {
		link(findSet(x), findSet(y));
	}
	
	public void link(int x, int y) {
		if (rank.get(x) > rank.get(y)) {
			p.put(y, x);
		} else {
			p.put(x, y);
			int rankY = rank.get(y);
			if (rank.get(x) == rankY) {
				rank.put(y, rankY + 1);
			}
		}
	}
	
	public int findSet(int x) {
		int px = p.get(x);
		if (x != px) {
			p.put(x, findSet(px));
		}
		return p.get(x);
	}

}
